package _interview150;

/**
 * 45. 跳跃游戏 II
 */
public class No45 {
    public int jump(int[] nums) {
        int n = nums.length;
        int start = 0, end = 0;
        int ans = 0;
        while (end < n - 1) {
            int curMaxIndex = end;
            for (int j = start; j <= end; j++) {
                if (j + nums[j] > curMaxIndex) {
                    curMaxIndex = j + nums[j];
                }
            }
            start = end + 1;
            end = curMaxIndex;
            ans++;
        }
        return ans;
    }
}
